The invention is generally related to the field of Electronic Design Automation as applied to the design of semiconductor chips, and more specifically, to a method for optimizing the placement of cells on the chip.
Placement has been an integral part of any VLSI chip design for many decades. Several approaches exist in the art for solving the placement problem. One of the most successful ones, known as partitioning, has been widely described in the technical literature, as for instance, by R. S. Tsay, E. S. Kuh and C. P. Hsu, “PROUD: a Sea-of-Gates Placement Algorithm”, published in IEEE Design & Test of Computers, Vol. 5, December 1988; by J. M. Kleinhans, G. Sigl and F. Johannes; “Gordian: A New Global Optimization/Rectangle Dissection Method for Cell Placement”, published in the Proceedings of the International Conference on Computer-Aided Design, pp. 506–509, 1988; and by G. Sigl, K. Doll and F. Johannes, “Analytical Placement: A Linear or Quadratic Objective Functions?”, published in the Proceedings of the Design Automation Conference, pp. 427–432, 1991.
An input to the placement process consists of a VLSI chip physical footprint that includes positioning the I/O (input/output) ports that connect the chip to the external world. Additionally, a description of the chip area is selected in order to assign physical locations corresponding to the circuits forming the chip. A second input consists of a chip level netlist that describes all the circuits that are to be placed. The description of the circuit includes attributes such as size, pin location, power connection ports and their respective locations. The netlist file also includes a description of the cell connectivity. In most instances, the location attribute is empty, and it is for the placement process to assign the locations. In some instances, cells in the netlist are preplaced at fixed locations, in which case the placement tool is expected to honor the location attribute according to the input data. The placement process assigns locations to all the objects present in the input netlist. The locations must be valid (i.e., legal) and non-overlapping, (i.e., the circuits must be placed in accordance to the description of the chip area—one of the inputs). Many such placement algorithms meeting these criteria are already in existence.
An ideal placement process is one that optimizes the characteristics of the VLSI chip by generating a routable placement characterized by having a minimum total wire length, a minimum timing cost, and a minimum signal integrity cost, wherein the cost is defined as a function of the following parameters:                a) the total wire length consisting of the sum of the wire lengths over all the nets of the netlist. Individual net lengths are computed using Steiner and Net-Half Perimeter methods. The Steiner wire length of a net is computed by generating a Steiner routing pattern, i.e., one that connects all of the pins on a net using horizontal and vertical line segments. These line segments may intersect each other at points that do not correspond to net pins. Such points are known as Steiner points. The length is then computed after the Steiner pattern is generated by adding the sum of the lengths of each individual horizontal and vertical line segment. This value is then used to represent the length of the net. The net-half-perimeter wire length refers to a method used for estimating the wire length. It involves creating a rectangle such that all the pins on the net remain within or at the boundary of the rectangle.        
Furthermore, the rectangle generated must be as small as possible and still satisfy all the aforementioned conditions. Finally, the perimeter of this rectangle is measured and halved, yielding a value known as the net-half-perimeter;                b) congestion, that defines the degree of routability of the design. Most commercial routers offer a global routing component providing this metric;        c) timing, that defines the intrinsic timing characteristics of the placement, computed by first repowering and buffering the design to be followed by a timing analysis; and        d) signal integrity, that qualifies the capacitive net coupling potential of the placement, and the probability of such coupling leading to functional and/or timing related problems.        
Referring now to FIG. 1 there is shown a representation of a conventional placement sequence.
Partitioning uses a “divide and conquer” approach to achieve its objectives. Initially, and referring to FIG. 1A, all the circuits are randomly placed on the chip regardless of the cost function optimization. In the case of a two-way partitioning (FIG. 1B), the chip is subdivided in two regions. The process of subdivision will be referred hereinafter as a “cut”. Starting from the rectangular outline of the entire chip, it is accomplished by drawing a vertical (or horizontal) line through the middle of the chip. The partitioning line together with the full chip outline defines the two regions. The next step consists in taking all the circuits falling within a window bounded by the two regions and assigns them to either region 1 or region 2 in a manner that minimizes the connectivity of the circuits in both regions. The remaining regions are then subdivided, as shown in FIGS. 1C–1E. The process proceeds recursively until each circuit is assigned a specific location in the chip. The process described thus far corresponds to the aforementioned two-way partitioning.
It is possible to perform two cuts at a time to achieve a four-way partitioning. The initial state of a four-way partitioning is based on circuits randomly placed on the chip that were previously shown in FIG. 1A. The placement step that follows corresponds to FIG. 1C, while the third state corresponds to FIG. 1E. This pattern continues until the end of the placement sequence is reached. The invention described herein applies to the general partitioning case that includes both, a two-way and a four-way partitioning.
In a more general way, a complete successive partitioning pass starts at cut 1 and terminates at cut N. Referring to FIG. 1B, the placement shown therein results from cut number 1, while FIGS. 1C–1E depict the results from cuts number 2, 3, and 4 This pattern continues until cut number N is reached, corresponding to a fully placed netlist, wherein the number of partitions is sufficiently small to specify its detailed placement qualities. The value of N is computed by the following equation 1:N=log2(image_area/smallest_cell_size)  (1)
The image area variable in equation (1) is a measure of the amount of circuitry that is to be placed on the chip. The smallest_cell_size variable is a measure of the area occupied by one occurrence of the cell. Dividing the image area by the smallest_cell_size, the maximum number of cells that can possibly be placed on the chip is determined. By taking the log2 of this number, the number of two-way partitioning operations required to have all the final partitions on the chip having only one cell is computed.
In previous generations of a VLSI design, placement was performed in a single stand-alone step, with a primary objective of generating a routable design (refer to the congestion cost metric described above) having a minimum total wire length. Since then, the technology trend has gravitated toward larger design sizes, concentrating rather on the chip performance determined by the inter-connect delay, and which is considered be a stronger function of the placement solution. Thus, the importance of optimizing the placement beyond the total wire length and congestion has now acquired a new and higher level of importance. As a result, placement algorithms are now imbedded into timing closure systems (like PDS, Magma's tools, Synopsys PD compiler, Cadence PKS, etc), where the placement itself is only one aspect of the optimization paradigm. These modern generation tools are designed to optimize the placement across many metrics, such as wire length, congestion, timing, and signal integrity.
Simultaneous optimization of the cost functions is difficult in view of certain cost functions competing against one another. By way of example, better timing may require extra wire length, which is in direct conflict with the goal of minimizing the wire length. The same can be said with regard to congestion and wire length, i.e., reducing congestion by increasing total wire length. In addition to internal cost function conflicts there are also other important optimizations such as timing, power, and signal integrity that are not easily visible to a native placement algorithm. For these reasons, it becomes more difficult to achieve the optimal placement.
Accordingly, there is a need for a general framework to achieve an optimal placement that specifically addresses optimizations that include global qualities of the placement solution, defined as those related to the most significant organization of logic placed on the VLSI chip. This need is particularly important for VLSI chips that include a hierarchy of logic functions. For instance, individual circuits are normally handled at the leaf level of the hierarchy. Moving up the hierarchy, there is a coarsening of the structure that reflects larger and larger logic groupings. It is this relative placement of larger logic groupings that defines the global qualities of the placement. The relative ordering and specific placement of circuits within the “larger logic groupings” relates to the local quality of the placement solution. It should be understood that the quality of the placement spans across a spectrum that includes global qualities on one end, and local qualities on the other. In the middle of the spectrum, there is a blend of global and local qualities.
Several approaches addressing congestion and timing optimization during placement are found in the literature. Techniques for optimization of congestion have been described, for instance, in:
U.S. Pat. No. 6,068,662, Method and Apparatus for Congestion Removal, issued to Scepanovic, et al;
U.S. Pat. No. 6,075,933, Method and Apparatus for Continuous Column Density Optimization, issued to Pavisic, et al.;
U.S. Pat. No. 6,123,736, Method and Apparatus for Horizontal Congestion Removal, issued to Pavisic, et al.; and
U.S. Pat. No. 6,070,108, Method and Apparatus for Congestion Driven Placement, issued Andreev, et al.
The techniques described therein involve the application of cell spreading following the placement step itself. A drawback of this approach is that they do not allow changes in the global qualities of the placement to be applied to the optimization. Post-placement techniques, such as cell spreading, do not alter the global component of the placement solution. They are valuable for other reasons, as described, e.g., in patent application Ser. No. 10/063,837, “Congestion Mitigation with Logic order Preservation” that falls in this category of algorithm.
Techniques for optimizing a placement based on timing considerations are described in several patents and can be divided into three categories. The first category generally involves the application of simple timing driven net weighting for placement followed by an in-place optimization (IPO) step. These approaches are limited in their ability to modify the global placement in order to achieve optimization. Examples can be found in:
U.S. Pat. No. 6,591,407, Method and Apparatus for Inter-connect-Driven Optimization of Integrated Circuit Design, issued to Kaufman, et al.;
U.S. Pat. No. 6,272,668, Method for Cell Swapping to Improve Pre-layout to Post-layout Timing, issued to Teene;
U.S. Pat. No. 6,263,478, System and Method for Generating and using Stage-Based Constraints for Timing-Driven Design, issued to Hahn, et al.;
U.S. Pat. No. 6,192,508, Method for Logic Optimization for Improving Timing and Congestion during Placement in Integrated Circuit Design, issued to Malik, et al.; and
U.S. Pat. No. 6,523,161, Method to Optimize Net Lists using Simultaneous Placement and Logic Optimization, issued to Gopalakrishnan, et al.
The second category applies recursive global placement and timing analysis during the forward progression of the algorithm. Examples of these are found in:
U.S. Pat. No. 6,415,426, Dynamic Weighting and/or Target Zone Analysis in Timing Driven Placement of Cells of an Integrated Circuit Design, issued to Chang, et al.;
U.S. Pat. No. 6,557,144, Netlist Re-synthesis Program Based on Physical Delay Calculation, issued to Lu, et al.;
U.S. Pat. No. 6,099,580, Method for Providing Performance-Driven Logic Optimization in and Integrated Circuit Layout Design, issued to Boyle, et al.; and
U.S. Pat. No. 5,654,898, Timing-Driven Integrated Circuit Layout through Device Sizing, issued to Roetcisoender, et al.
The third category uses dynamic net weight adjustment and simple logic optimization during placement. Examples are found in: U.S. Pat. No. 6,601,226, Tight Loop Method of Timing Driven Placement, issued to Hill, et al.;
U.S. Pat. No. 5,666,290, Interactive Timing-Driven Method of Component Placement that more directly constrains Critical Paths using Net-Based Constraints, issued to Li, et al.; and
U.S. Pat. No. 6,286,128, Method for Design Optimization using Logical and Physical Information, issued to Pileggi, et al.
The referenced patents categorized in the three afore-mentioned categories lack the all important “look ahead” characteristic which forms the basis for an efficient optimization, and which includes those related to timing optimization and congestion optimization. The look ahead technique allows the process to closely control the optimization qualities result thereof.